import java.util.Arrays;

public class J101203 {
    // 选择排序
    public static void selectSort(int[] array){
        // write code  here
       for(int i = 0; i < array.length - 1; i++){
           int mix = i;
           for(int j = i + 1; j < array.length; j++){
               if(array[j] < array[mix]){
                   mix = j;
               }
           }
           int tmp = array[mix];
           array[mix] = array[i];
           array[i] = tmp;
       }
    }


// 堆排序
    public static void heapSort(int[] array){
        // write code  here
        int len = array.length;
        for(int i = (len - 2) / 2; i >= 0; i--){
            shiftDown(array, i, len);
        }
        for(int i = 0; i < array.length; i++){
            if(array[0] > array[len - 1]) {
                int tmp = array[0];
                array[0] = array[len - 1];
                array[len - 1] = tmp;
            }
            shiftDown(array, 0, --len);
        }
    }

    public static void shiftDown(int[] array, int start, int length) {
        int parent = start;
        // 左孩子索引
        int child = 2 * parent + 1;
        while (child < length) {
            // 如果右孩子存在且值更大，选择右孩子
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }

            // 如果父节点值大于等于子节点中最小值，说明符合堆结构，退出
            if (array[parent] >= array[child]) {
                break;
            }

            // 否则交换父节点和子节点的值
            int temp = array[parent];
            array[parent] = array[child];
            array[child] = temp;

            // 继续向下处理
            parent = child;
            child = 2 * parent + 1;
        }
    }

    public static void main(String[] args) {
        int[] nums= new int[]{5,2,3,0,9,8,1,6,4,7};
//        selectSort(nums);
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
